import java.util.*;


/**
 * Created with IntelliJ IDEA.
 * User: 12629
 * Date: 2021/11/3
 * Time: 8:56
 * Description:
 */
class MyStack {

    private Queue<Integer> qu1;
    private Queue<Integer> qu2;
    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    public void push(int x) {
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        }else if(!qu2.isEmpty()) {
            qu2.offer(x);
        }else{
            qu1.offer(x);
        }
    }

    public int pop() {
        if(empty()) {
            return-1;
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for(int i = 0;i < size-1;i++) {
                int val = qu1.poll();
                qu2.offer(val);
            }
            return qu1.poll();
        }else{
            int size = qu2.size();
            for(int i = 0;i < size-1;i++) {
                int val = qu2.poll();
                qu1.offer(val);
            }
            return qu2.poll();
        }
    }

    public int top() {
        if(empty()) {
            return-1;
        }
        int tmp = 0;
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for(int i = 0;i < size;i++) {
                tmp = qu1.poll();
                qu2.offer(tmp);
            }
        }else{
            int size = qu2.size();
            for(int i = 0;i < size;i++) {
                tmp = qu2.poll();
                qu1.offer(tmp);
            }
        }
        return tmp;
    }

    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}
class MyQueue {

    private Stack<Integer> s1;//入队的栈
    private Stack<Integer> s2;//出队的栈

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if(empty()) {
            return -1;
        }
        if(s2.isEmpty()) {
            while(!s1.isEmpty()) {
                int val = s1.pop();
                s2.push(val);
            }
        }
        return s2.pop();
    }

    public int peek() {
        if(empty()) {
            return -1;
        }
        if(s2.isEmpty()) {
            while(!s1.isEmpty()) {
                int val = s1.pop();
                s2.push(val);
            }
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}
class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        //1、普通栈 一定要放
        stack.push(val);
        if(minStack.isEmpty()) {
            minStack.push(val);
        }else{
            //
            int top = minStack.peek();
            if(top >= val) {
                minStack.push(val);
            }
        }
    }
    //针对的是普通的栈
    public void pop() {
        if(stack.isEmpty()) {
            return;
        }
        int tmp = stack.pop();
        if(tmp == minStack.peek()) {
            minStack.pop();
        }
    }
    //针对的是普通的栈
    public int top() {
        if(stack.isEmpty()) {
            return -1;
        }
        return stack.peek();
    }

    public int getMin() {
        if(minStack.isEmpty()) {
            return -1;
        }
        return minStack.peek();
    }
}
public class TestDemo {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < s.length();i++) {
            char ch = s.charAt(i);
            if(ch=='(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else{
                if(stack.empty()) {
                    System.out.println("右括号多");
                    return false;
                }
                char top = stack.peek();//(    {    [
                if(ch==')' && top=='(' || ch=='}' && top=='{' || ch==']' && top=='[') {
                    stack.pop();
                }else{
                    System.out.println("左右括号次序不对！");
                    return false;
                }
            }
        }
        if(!stack.empty()){
            System.out.println("左括号多！");
            return false;
        }
        return true;
    }
    public static void main(String[] args) {

    }
}
